package com.epam.rd.myCollections.map;

import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

public class MyHashMap implements MyMap {
	static final int DEFAULT_INITIAL_CAPACITY = 16;
	static final int MAXIMUM_CAPACITY = 100;
	static final float DEFAULT_LOAD_FACTOR = 0.75f;
	transient Entry[] table;
	transient int size;
	int threshold;
	final float loadFactor;

	public MyHashMap() {
		this.loadFactor = DEFAULT_LOAD_FACTOR;
		threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
		table = new Entry[DEFAULT_INITIAL_CAPACITY];
	}

	public MyHashMap(int initialCapacity, float loadFactor) {
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: "
					+ initialCapacity);
		if (initialCapacity > MAXIMUM_CAPACITY)
			throw new IllegalArgumentException("Illegal load factor: "
					+ loadFactor);
		if (loadFactor <= 0)
			throw new IllegalArgumentException("Illegal load factor: "
					+ loadFactor);

		// Find a power of 2 >= initialCapacity
		int capacity = 1;
		while (capacity < initialCapacity)
			capacity <<= 1;

		this.loadFactor = loadFactor;
		threshold = (int) (capacity * loadFactor);
		table = new Entry[capacity];
	}

	public void clear() {
		Entry[] tab = table;
		for (int i = 0; i < tab.length; i++)
			tab[i] = null;
		size = 0;
	}

	public boolean containsKey(Object key) {
		return getEntry(key) != null;
	}

	final Entry getEntry(Object key) {
		int hash = (key == null) ? 0 : hash(key.hashCode());
		for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash
					&& ((k = e.key) == key | (key != null && key.equals(k)))) {
				return e;
			}
		}
		return null;
	}

	public boolean containsValue(Object value) {
		if (value == null)
			return containsNullValue();

		Entry[] tab = table;
		for (int i = 0; i < tab.length; i++)
			for (Entry e = tab[i]; e != null; e = e.next)
				if (value.equals(e.getValue()))
					return true;
		return false;
	}

	private boolean containsNullValue() {
		Entry[] tab = table;
		for (int i = 0; i < tab.length; i++)
			for (Entry e = tab[i]; e != null; e = e.next)
				if (e.value == null)
					return true;
		return false;
	}

	public Object get(Object key) {
		if (key == null)
			return getForNullKey();
		int hash = hash(key.hashCode());
		for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash & ((k = e.key) == key | key.equals(k)))
				return e.value;
		}
		return null;
	}

	private Object getForNullKey() {
		for (Entry e = table[0]; e != null; e = e.next) {
			if (e.key == null)
				return e.getValue();
		}
		return null;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public Object put(Object key, Object value) {
		if (key == null)
			return putForNullKey(value);
		int hash = hash(key.hashCode());
		int i = indexFor(hash, table.length);
		for (Entry e = table[i]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash) {
				k = e.getKey();
				if (k == key | key.equals(k)) {
					Object oldValue = e.getValue();
					e.value = value;
					return oldValue;
				}
			}
		}

		addEntry(hash, key, value, i);
		return null;
	}

	static int hash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	private Object putForNullKey(Object value) {
		for (Entry e = table[0]; e != null; e = e.next) {
			if (e.key == null) {
				Object oldValue = e.getValue();
				e.setValue(value);
				return oldValue;
			}
		}
		addEntry(0, null, value, 0);
		return null;
	}

	void addEntry(int hash, Object key, Object value, int bucketIndex) {
		Entry e = table[bucketIndex];
		table[bucketIndex] = new Entry(hash, key, value, e);
		if (size++ >= threshold)
			resize(2 * table.length);
	}

	void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;

		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

	void transfer(Entry[] newTable) {
		Entry[] src = table;
		int newCapacity = newTable.length;
		for (int j = 0; j < src.length; j++) {
			Entry e = src[j];
			if (e != null) {
				src[j] = null;
				do {
					Entry next = e.next;
					int i = indexFor(e.hash, newCapacity);
					e.next = newTable[i];
					newTable[i] = e;
					e = next;
				} while (e != null);
			}
		}
	}

	static int indexFor(int h, int length) {
		return h & (length - 1);
	}

	public Object remove(Object key) {
		Entry e = removeEntryForKey(key);
		return (e == null ? null : e.getValue());
	}

	final Entry removeEntryForKey(Object key) {
		int hash = (key == null) ? 0 : hash(key.hashCode());
		int i = indexFor(hash, table.length);
		Entry prev = table[i];
		Entry e = prev;

		while (e != null) {
			Entry next = e.next;
			Object k;
			if (e.hash == hash
					&& ((k = e.key) == key | (key != null && key.equals(k)))) {
				size--;
				if (prev == e)
					table[i] = next;
				return e;
			}
			prev = e;
			e = next;
		}

		return e;
	}

	public int size() {
		return size;
	}

	public Iterator entryIterator() {
		return new HashIterator();
	}

	private class HashIterator implements Iterator {
		Entry next; 
		int index;
		Entry current;

		HashIterator() {
			
			if (size > 0) {
				Entry[] t = table;
				while (index < t.length && (next = t[index++]) == null)
					;
			}
		}

		final Entry nextEntry() {
			Entry e = next;
			if (e == null)
				throw new NoSuchElementException();

			if ((next = e.next) == null) {
				Entry[] t = table;
				while (index < t.length && (next = t[index++]) == null)
					;
			}
			current = e;
			return e;
		}

		public void remove() {
			if (current == null)
				throw new IllegalStateException();
			Object k = current.key;
			current = null;
			MyHashMap.this.removeEntryForKey(k);
		}

		public Object next() {
			return nextEntry().key;
		}

		public boolean hasNext() {
			return next != null;
		}
	}

	static class Entry implements MyMap.Entry {
		final Object key;
		Object value;
		Entry next;
		final int hash;

		Entry(int h, Object k, Object v, Entry n) {
			value = v;
			next = n;
			key = k;
			hash = h;
		}

		public Object getKey() {
			return key;
		}

		public Object getValue() {
			return value;
		}

		public Object setValue(Object newValue) {
			Object oldValue = value;
			value = newValue;
			return oldValue;
		}

	}
}
